#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<int> minp, primes;

void sieve(int n) {
    minp.assign(n + 1, 0);
    primes.clear();
    for (int i = 2; i <= n; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            primes.push_back(i);
        }
        for (auto p : primes) {
            if (1LL * i * p > n) break;
            minp[i * p] = p;
            if (p == minp[i]) break;
        }
    }
}

unordered_set<int> get_factors(int x) {
    unordered_set<int> factors;
    if (x < 2) return factors;
    if (x <= 2e5+5) {
        while (x > 1) {
            int p = minp[x];
            factors.insert(p);
            while (x % p == 0) x /= p;
        }
    } else {
        for (auto p : primes) {
            if (1LL * p * p > x) break;
            if (x % p == 0) {
                factors.insert(p);
                while (x % p == 0) x /= p;
            }
        }
        if (x > 1) factors.insert(x);
    }
    return factors;
}

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1); 
    vector<int> b(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];

    unordered_map<int, int> mp;
    for (int i = 1; i <= n; i++) {
        auto f = get_factors(a[i]);
        for (auto p : f) {
            mp[p]++;
            if (mp[p] >= 2) {
                cout << 0 << '\n';
                return;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        auto factors = get_factors(a[i] + 1);
        for (auto p : factors) {
            if (mp.count(p)) { 
                cout << 1 << '\n';
                return;
            }
        }
    }

    cout << 2 << '\n';
}

int main() {
    sieve(2e5 + 10);
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}